load balancing

operating system, parallel Techniques which aim to spread

tasks among the processors in a parallel processor to avoid

some processors being idle while others have tasks queueing

for execution. Load balancing may be performed either by

heavily loaded processors (with many tasks in their queues)

sending tasks to other processors; by idle processors

requesting work from others; by some centralised task

distribution mechanism; or some combination of these. Some

systems allow tasks to be moved after they have started

executing ("task migration") others do not. It is important

that the overhead of executing the load balancing

algorithm does not contribute significantly to the overall

processing or communications load.

Distributed scheduling algorithms may be static, dynamic or

preemptive. Static algorithms allocate processes to

processors at run time while taking no account of current

network load. Dynamic algorithms are more flexible, though

more computationally expensive, and give some consideration to

the network load before allocating the new process to a

processor. Preemptive algorithms are more expensive and

flexible still, and may migrate running processes from one

host to another if deemed beneficial. Research to date

indicates that dynamic algorithms yield significant

performance benefits, but that further (though lesser) gains

may be had through the addition of process migration

facilities.

(1995-03-13)